#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//创建新节点
SLTNode* BuySListNode(SLTDataType x)
{
	//用malloc开辟一个大小为SLTNode的空间给newnode
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//将用户想要的x值赋给data
	newnode->data = x;
	//将新节点的next指向NULL
	newnode->next = NULL;

	return newnode;
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	//断言
	assert(pphead);
	//创建一个新节点，其值为用户自定义的x
	SLTNode* newnode = BuySListNode(x);

	//将newnode指向一开始头指针指向的节点
	newnode->next = *pphead;
	//再把头指针指向这个头插的节点newnode
	*pphead = newnode;

}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	//断言
	assert(pphead);
	//创建一个新节点，其值为用户自定义的x
	SLTNode* newnode = BuySListNode(x);

	//第一种情况：链表为NULL
	if (*pphead == NULL)
	{
		(*pphead)->next = newnode;
	}
	//第一种情况：链表不为NULL
	else
	{
		//找到尾节点
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//将尾节点指向新尾插的节点
		tail->next = newnode;
	}
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	//断言
	assert(pphead);
	assert(*pphead);

	//创建一个新的头指针去指向第二个节点
	SLTNode* newhead = (*pphead)->next;
	//释放掉原本头指针指向的第一个节点
	free(*pphead);
	//再用新的头指针去更新原本的头指针
	*pphead = newhead;
}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	//只有一个节点的情况
	if ((*pphead)->next == NULL)
	{
		//释放掉第一个节点的内容
		free(*pphead);
		//将头指针置空
		*pphead = NULL;
	}
	//不止一个节点的情况
	else
	{
		//创建两个指针
		SLTNode* tail = *pphead;
		SLTNode* tailprev = NULL;
		//找到尾节点
		while (tail->next != NULL)
		{
			//将tail指针给tailprev，然后tail自己往后走
			tailprev = tail;
			tail = tail->next;
			//找到尾节点之后，两个指针的停留位置，一前一后，
			//一个指向尾节点，一个指向尾节点的前一个节点
		}
		//释放尾节点
		free(tail);
		//将指向尾节点的指针置空
		tail = NULL;
		//将尾删后的尾节点next改为NULL
		tailprev->next = NULL;
		//方法二：
		/*
		//创建一个指针
		SLTNode* tail = *pphead;
		找到倒数第二个节点
		while (tail->next->next)
		{
			tail = tail->next;
		}
		将尾节点释放
		free(tail->next);
		将指向尾节点的指针置空
		tail->next = NULL;
		*/
	}
}

//查找是否存在某节点的值为x
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	//用形参头指针phead去遍历查找
	SLTNode* cur = phead;
	//cur为空才停下来，这样才能将尾节点的值也进行了比对
	while (cur)
	{
		if (cur->data == x)
		{
			//找到就返回cur指向的节点
			return cur;
		}
		//让cur往后移动
		cur = cur->next;
	}
	//找不到返回NULL
	return NULL;
}

//在pos节点之前插入一个值为x的节点
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	//断言
	assert(pphead);
	assert(pos);

	//情况一：头插（在第一个节点前插入）
	if (pos == *pphead)
	{
		//复用头插
		SLTPushFront(pphead, x);
	}
	//情况二：其他节点前的插入
	else
	{
		// 创建一个指针
		SLTNode* prev = *pphead;
		//找到pos节点的前一个节点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//插入的新节点的创建
		SLTNode* newnode = BuySListNode(x);
		//将pos节点的前一个节点指向newnode
		prev->next = newnode;
		//将插入的新节点指向pos节点
		newnode->next = pos;
	}
}

//在pos节点之后插入一个值为x的节点
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	//断言
	assert(pos);
	//新节点的创建
	SLTNode* newnode = BuySListNode(x);
	//新节点指向之前pos指向的节点
	newnode->next = pos->next;
	//pos节点指向新的节点
	pos->next = newnode;
}

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	//断言
	assert(pphead);
	assert(pos);
	//情况1：头删（pos为第一个节点）
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	//情况2：其他位置节点的删除
	else
	{
		//创建一个指针
		SLTNode* prev = *pphead;
		//找到pos的前一个节点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//将pos前一个节点指向pos的后面一个节点
		prev->next = pos->next;
		//释放掉pos节点
		free(pos);
		//pos = NULL;
	}
}

// 删除pos节点的后一个节点
void SLTEraseAfter(SLTNode* pos)
{
	//断言检查pos和pos是否是尾节点
	assert(pos);
	assert(pos->next);
	//创建一个指针指向pos节点的下一个节点
	SLTNode* posNext = pos->next;
	//将pos节点指向pos的下一个节点的下一个节点
	pos->next = posNext->next;
	//释放掉pos节点的下一个节点
	free(posNext);
	//将指向pos节点的下一个节点的指针置空
	posNext = NULL;
}

//打印单链表
void SLTPrint(SLTNode* phead)
{
	//不需要断言，有可能本身就是空链表
	SLTNode* cur = phead;

	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}

	printf("NULL\n");
}